A path in an edge-colored graph is called {\em rainbow} if no two edges of itare colored the same. For an $\ell$-connected graph $G$ and an integer $k$ with$1\leq k\leq \ell$, the {\em rainbow $k$-connection number} $rc_k(G)$ of $G$ isdefined to be the minimum number of colors required to color the edges of $G$such that every two distinct vertices of $G$ are connected by at least $k$internally disjoint rainbow paths. Fujita et. al. proposed a problem that whatis the minimum constant $\alpha>0$ such that for all 2-connected graphs $G$ on$n$ vertices, we have $rc_2(G)\leq \alpha n$. In this paper, we prove that$\alpha=1$ and $rc_2(G)=n$ if and only if $G$ is a cycle of order $n$, settlingdown this problem.
展开▼
机译:如果没有两个边缘的颜色相同,则将边缘颜色的图中的路径称为{\ em rainbow}。对于具有$ \ ell $连通图$ G $和带有$ 1 \ leq k \ leq \ ell $的整数$ k $,{G的$ k $连接数} $ G的$ rc_k(G)$ $定义为为$ G $的边缘着色所需的最小颜色数,以使$ G $的每两个不同的顶点之间通过至少$ k $内部不相交的彩虹路径相连。藤田等等提出了一个最小常数$ \ alpha> 0 $的问题,这样对于所有2个连通图$ G $ on $ n $顶点,我们有$ rc_2(G)\ leq \ alpha n $。在本文中,我们证明$ \ alpha = 1 $和$ rc_2(G)= n $当且仅当$ G $是一个订单$ n $的循环时,才解决了这个问题。
展开▼